package dichotomy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;

public class DichotomyNotSortFind {

    private static int dichotomy(int[] arr, int find) {
        /**
         * 如果数组中没有数据或者只有一个数据，那么就不需要比较了。
         */
        if (null == arr || arr.length == 0) {
            return -1;
        }

        int left = 0; // 数组最小下标
        int right = arr.length - 1; // 数组最大下标
        int middle; // 中间值下标
        while (left <= right) {
            /**
             * 中间值下标计算方法：为避免left+right内存溢出，利用left + ((right - left) / 2)代替，
             * 以肯定程度上可以避免溢出问题。
             * middle = left + ((right - left) / 2) <=> middle = left + ((right - left) >> 2);
             */
            middle = left + ((right - left) / 2);
            if (arr[middle] > find) { // 如果中间值比要找的值大，说明要找的值在中间值的左侧
                right = middle - 1;
            } else if (arr[middle] < find) { // 如果中间值比要找的值小，说明要找的值在中间值的右侧
                left = middle + 1;
            } else {
                return middle; // 如果中间值和要找的值相等，说明要找的值就是该下标对应的值
            }
        }

        return left;
    }

    @Test
    public void client() {
        Random random = new Random(1);
        for (int i = 0; i < 500000; i++) {
            /**
             * 随机样本长度
             */
            int anInt = random.nextInt(100) + 1;
            int[] arr = new int[anInt];
            for (int j = 0; j < anInt; j++) {
                /**
                 * 随机样本数据
                 */
                arr[j] = random.nextInt(100);
            }
            System.out.println("=======================第" + (i + 1) + "次=======================");
            int findIndex = random.nextInt(arr.length);
            int findData = arr[findIndex];
            System.out.println("排序后==》" + Arrays.toString(arr));
            System.out.println("随机产生的查找数据为==》" + findData + "==》索引位置为" + findIndex);
            int index = dichotomy(arr, findData);
            if (index >= 0 && index < arr.length) {
                int dichotomy = arr[index];
                System.out.println("二分法查找数据为==》" + dichotomy + "==》索引位置为" + index);
            } else {
                System.out.println("二分法查找数据为==》" + null + "==》索引位置为" + index);
            }
            if (findIndex == index) {
                System.out.println("对数器验证结果：PASS");
            } else {
                System.out.println("对数器验证结果：NOT PASS（这里应该是对的， 只是索引位置不对）");
            }
        }
    }
}
